Hitherto, an encoding method and encryption method having messages that are public and non-commutative has been known (Japanese Patent Application Laid-Open (JP-A) 2001-202010). Public key encryption systems employing finite commutative groups, and public key encryption systems employing a non-commutative ring R are also known (Japanese National-Phase Publication Nos. 2004-534971, 2000-516733).
An over-network exchange verification and public key exchange system according to a public key encryption protocol, and key management of a public key encryption system based on a control vector are also known (JP-A Nos. 2006-262425, H05-216409).